package com.longge;

public class InsertGreatestCommonDivisors {

    public ListNode insertGreatestCommonDivisors(ListNode head) {


        ListNode cur = head;

        while (cur != null && cur.next != null) {
            int val = gcd(cur.val, cur.next.val);
            ListNode temp = cur.next;
            cur.next = new ListNode(val);
            cur.next.next=temp;
            cur=temp;
        }
        return head;
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}
